The invention relates generally to pseudo-random number generation and more particularly to pseudo-random number generators operating efficiently in software and having efficient hardware implementations, for generating enciphered data streams.
When a pseudo-random sequence is used as a stream cipher for encryption, the same sequence must be generated to decrypt the data stream as was used to encrypt it. In the case where the encrypted data is being passed between two devices, both the sending device and the receiving device must be capable of creating identical pseudo-random sequences. In some applications, it occurs that one of the communicating devices is a general-purpose computer while the other includes a piece of special purpose hardware for generating pseudo-random sequences. In such circumstances, it is desirable that identical pseudo-random sequences can be generated efficiently both in hardware and in software implementations.
One such example application is the transmittal of copyright-protected digital video streams between a consumer electronics playback device, such as a digital video disk (DVD) player, and a personal computer, wherein the data is encrypted in transit between the two devices in order to protect it from unauthorized copying. The encryption function is desirably performed without significant cost impact on the consumer electronics device, and without undue computational burden on the personal computer. In particular, digital video streams are typically transmitted in a compressed format, and a personal computer may need almost all of its computational power simply to perform the decompression operation. An acceptable hardware cost for such an application may be as little as 1000 to 2000 gates, while the required throughput in software may be in excess of two bits per cycle on a general purpose computer.
A class of pseudo-random generators that achieve exceptional performance in software, in part through efficiently exploiting instruction-level parallelism in processors, is described in my co-pending provisional application No. 60/037,746, filed on Jan. 17, 1997 and assigned to the present assignee, the contents of which are incorporated herein by reference. These generators are pseudo-random non-linear state machines constructed from two component types: non-linear w-bit mixing functions, and w-bit registers, where for efficiency of implementation in software, w can be chosen to be the native word-length of the datapaths of the target processors.
As described in my co-pending application, in typical software embodiments suited for 32-bit processors, and referring to FIG. 1a, these generators have four 32-bit mixing functions 10 and four or five 32-bit registers 20. In a straightforward hardware implementation of such a generator, each mixing function would be implemented by a non-linear combiner consisting of a 32-bit adder, an array of thirty-two 2-input exclusive-OR gates, and a look-up-table of 256 entries each of 32 bits. If one bit of memory is counted as being equivalent to one logic gate, then a single non-linear combiner alone uses substantially more than 8000 gates. Taking all the non-linear combiners and associated registers together, the accumulated gate count for a generator is on the order of 40,000 gates.
It is therefore an object of the invention to provide a hardware efficient pseudo-random number generator capable of emulating a pseudo-random number generator adapted for efficient implementation in software on a processor capable of instruction-level parallelism. In particular, it is an object of the invention to provide such a generator having a minimal number of non-linear combiners, and to provide a non-linear combiner using a reduced amount of lookup table memory.